package com.demo.algorithm.dfs02;

import java.util.LinkedList;
import java.util.List;

/**
 * Description: 回溯算法——全排列
 *
 * @Date: 2021/4/30 23:28
 * @Author: zsyoung@qq.com
 */
public class Quanpailie {
    private static List<List<Integer>> res = new LinkedList<>();

    /**
     * 主函数，输入一组不重复的数字，会返回他们的全排列
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        //记录路径
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;

    }

    /**
     * 路径：记录在 track 中
     * 选择列表：nums 中不存在于 track 中的那些元素
     * 结束条件：nums 中的元素全部在 track 中出现
     *
     * @param nums
     * @param track
     */
    private static void backtrack(int[] nums, LinkedList<Integer> track) {
        //触发结束条件
        if (nums.length == track.size()) {
            res.add(new LinkedList<Integer>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (track.contains(nums[i])) {
                continue;
            }
            //做选择
            track.add(nums[i]);
            //进入下一层决策树
            backtrack(nums, track);
            System.out.println("track = " + track);
            //取消选择
            track.removeLast();
        }

    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permute = permute(nums);
        System.out.println("permute.toString() = " + permute.toString());
    }


}
